#define _CRT_SECURE_NO_WARNINGS 1
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)
        return NULL;

    struct Node* cur = head;
    struct Node* mem = NULL;

    struct Node* phead = (struct Node*)malloc(sizeof(struct Node));
    phead->next = NULL;

    mem = phead;
    while (cur)
    {
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));

        newnode->val = cur->val;
        newnode->next = cur->next;

        phead->next = newnode;
        phead = newnode;

        cur = newnode->next;
    }

    struct Node* Head = head;
    phead = mem;
    while (head)
    {
        phead = phead->next;
        cur = Head;

        if (head->random == NULL)
        {
            phead->random = NULL;
            head = head->next;
            continue;
        }
        int count = 0;
        while (cur != head->random)
        {
            count++;
            cur = cur->next;
        }
        cur = mem->next;
        while (count--)
        {
            cur = cur->next;
        }
        phead->random = cur;
        head = head->next;
    }

    phead = mem;
    mem = phead->next;
    free(phead);
    return mem;

}